#include <cctype>
#include <iostream>
#include <stack>
using namespace std;

typedef struct BiNode {
    char data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;


bool In(char ch); 
char GetTop(stack<char> s); 
int Precede(char op1, char op2); 
void CreateExpTree(BiTree& T, BiTree a, BiTree b, char theta); 
int GetValue(char op, int l, int r);    

void InitExpTree(BiTree& T)
{
    char ch;
    stack<BiTree> EXPT; 
    stack<char> OPTR; 
    OPTR.push('#');

    cin >> ch;
    while (ch != '#' || GetTop(OPTR) != '#') {
        if (!In(ch)) { 
            BiTree leaf = new BiNode;
            leaf->data = ch;
            leaf->lchild = leaf->rchild = nullptr;
            EXPT.push(leaf);
            cin >> ch;
        } else { 
            switch (Precede(GetTop(OPTR), ch)) {
            case '<': 
                OPTR.push(ch);
                cin >> ch;
                break;
            case '>': { 
                char theta = OPTR.top();
                OPTR.pop();
                BiTree b = EXPT.top();
                EXPT.pop();
                BiTree a = EXPT.top();
                EXPT.pop();
                BiTree node = new BiNode;
                node->data = theta;
                node->lchild = a;
                node->rchild = b;
                EXPT.push(node);
                break;
            }
            case '=': 
                OPTR.pop();
                cin >> ch;
                break;
            }
        }
    }
    T = EXPT.top(); 
}

int EvaluateExpTree(BiTree t)
{
    if (t->lchild == nullptr && t->rchild == nullptr) {
        return t->data - '0';
    }
    int lvalue = EvaluateExpTree(t->lchild);
    int rvalue = EvaluateExpTree(t->rchild);
    return GetValue(t->data, lvalue, rvalue);
}

bool In(char ch)
{
    return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')' || ch == '#';
}

char GetTop(stack<char> s)
{
    if (s.empty())
        return '#';
    return s.top();
}

int Precede(char op1, char op2)
{
    const char priority[7][7] = {
        // +   -   *   /   (   )   #
        { '>', '>', '<', '<', '<', '>', '>' }, // +
        { '>', '>', '<', '<', '<', '>', '>' }, 
        { '>', '>', '>', '>', '<', '>', '>' }, 
        { '>', '>', '>', '>', '<', '>', '>' }, 
        { '<', '<', '<', '<', '<', '=', ' ' },
        { '>', '>', '>', '>', ' ', '>', '>' }, 
        { '<', '<', '<', '<', '<', ' ', '=' } 
    };

    int i, j;
    switch (op1) {
    case '+':
        i = 0;
        break;
    case '-':
        i = 1;
        break;
    case '*':
        i = 2;
        break;
    case '/':
        i = 3;
        break;
    case '(':
        i = 4;
        break;
    case ')':
        i = 5;
        break;
    case '#':
        i = 6;
        break;
    }
    switch (op2) {
    case '+':
        j = 0;
        break;
    case '-':
        j = 1;
        break;
    case '*':
        j = 2;
        break;
    case '/':
        j = 3;
        break;
    case '(':
        j = 4;
        break;
    case ')':
        j = 5;
        break;
    case '#':
        j = 6;
        break;
    }
    return priority[i][j];
}

void CreateExpTree(BiTree& T, BiTree a, BiTree b, char theta)
{
    T = new BiNode;
    T->data = theta;
    T->lchild = a;
    T->rchild = b;
}

int GetValue(char op, int l, int r)
{
    switch (op) {
    case '+':
        return l + r;
    case '-':
        return l - r;
    case '*':
        return l * r;
    case '/':
        return l / r;
    default:
        return 0;
    }
}

int main()
{
    BiTree T;
    cout << "输入表达式(以#结束，如：3*(7-2)#): ";
    InitExpTree(T);
    cout << "表达式结果: " << EvaluateExpTree(T) << endl;
    return 0;
}

